import java.awt.image.BandCombineOp;

// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
public class BalancedBinaryTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static boolean balance;

    public boolean isBalanced(TreeNode root) {
        balance = true;   //默认是平很二叉树
        func(root);
        return balance;
    }

    public int func(TreeNode cur){
        if(cur == null || !balance){ //如果节点为空或者不平衡了直接返回，返回什么数不重要
            return 0;
        }
        int lh = func(cur.left);   //左子树的高度
        int rh = func(cur.right);  //右子树的高度
        if (Math.abs(lh-rh) > 1){
            balance = false;        //左右子树高度差大于1就修改为不平衡
            return 0;//不平衡就直接返回
        }
        return Math.max(lh,rh)+1; //向上返回当前节点开始到叶子节点的高度
    }
}
